package com.newegg.research.KMP;

public class KMP_Algorithm
{
	public static int[] getNextValue(final String input)
	{
		char[] cs = input.toCharArray();
		int[] next = new int[cs.length];
		next[0] = -1;
		int j = 0, k = -1;
		while (j < cs.length - 1)
		{
			if (k == -1 || cs[j] == cs[k])
			{
				++j;
				++k;
				if (cs[j] != cs[k])
					next[j] = k;
				else
					next[j] = next[k];
			} else
				k = next[k];
		}
		return next;
	}

	public static void main(String[] args)
	{
		int[] s = getNextValue("ababcaabc");
		for (int i : s)
		{
			System.out.print(i + ",");
		}
	}
}
